package com.ksm.algorithm.binarysearch;

public class BinarySearch {
    public static int binarySearchBasic(int[] arr, int target) {
        //初始化并赋初值i , j
        int i = 0, j = arr.length - 1;
        //循环条件：i <= j
        while (i <= j) {
            //每次循环先计算中间索引值，java里两整数相处自动向下取整
            int mid = (i + j) >>> 1;
            //三个分支：比对成功直接返回，中间索引值大于或小于target,改变i / j位置，再次循环
            if (arr[mid] == target) {
                return mid;
            } else if (target < arr[mid]) {
                j = mid - 1;
            } else if (arr[mid] < target) {
                i = mid + 1;
            }
        }
        return -1;
    }

    public static int binarySearchAlternative(int[] arr, int target) {
        //初始化并赋初值i , j
        int i = 0, j = arr.length;
        //循环条件：i < j
        while (i < j) {
            //每次循环先计算中间索引值，java里两整数相处自动向下取整
            int mid = (i + j) >>> 1;
            //三个分支：比对成功直接返回，中间索引值大于或小于target,改变i / j位置，再次循环
            if (arr[mid] == target) {
                return mid;
            } else if (target < arr[mid]) {
                j = mid;
            } else if (arr[mid] < target) {
                i = mid + 1;
            }
        }
        return -1;
    }

    public static int binarySearchBalance(int[] a, int target) {
        int i = 0, j = a.length;//i闭区间 j开区间
        //每次循环计算 i 与 j 是否紧挨，如果紧挨说明i指向了最后一个待比较元素，这个元素要么是target要么不是
        while (1 < j - i) {
            int m = (i + j) >>> 1;//计算中间索引
            if (target < a[m]) {//只需要一次比较，比较失败直接走else无需额外的比较
                j = m;
            } else {
                i = m;
            }
        }
        //最后再进行判断target值
        return (a[i] == target) ? i : -1;
    }

    public static int binarySearchLeftmost1(int[] a, int target) {
        int i = 0, j = a.length - 1;
        //标记作用，每次临时记录与target相等的位置
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                candidate = m; // 记录候选位置
                j = m - 1; // 继续向左，再次进行二分查找，如果有匹配的就记录，没有就退出循环
            }
        }
        return candidate;
    }

    public static int binarySearchRightmost1(int[] a, int target) {
        int i = 0, j = a.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                candidate = m; // 记录候选位置
                i = m + 1; // 继续向右
            }
        }
        return candidate;
    }

    public static int binarySearchLeftmost(int[] a, int target) {
        int i = 0, j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            //这里判断条件改变了，只要target是小于等于中间索引值，范围都往左缩小
            if (target <= a[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i;
    }

    public static int binarySearchRightmost(int[] a, int target) {
        int i = 0, j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            //这里同理只要target是大于等于中间索引值，范围都往右缩小
            if (target < a[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i - 1;
    }
}
